package leetcode.code0381;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class RandomizedCollection2 {

	Map<Integer, List<Integer>> ids;
	List<Integer> nums;
	int size;

	public RandomizedCollection2() {
		ids = new HashMap<>();
		nums = new ArrayList<>();
		size = 0;
	}

	// 题目未说清返回值意义，示例中找线索
	public boolean insert(int val) {
		List<Integer> id = ids.getOrDefault(val, new ArrayList<Integer>());
		id.add(size);
		ids.put(val, id);
		size += 1;
		nums.add(val);
		return id.size() == 1;
	}

	// 题目未说清返回值意义，示例中也未说清
	public boolean remove(int val) {
		List<Integer> id = ids.getOrDefault(val, null);
		if (id == null) {
			return false;
		}
		size -= 1;
		int index = id.get(id.size() - 1);
		id.remove(id.size() - 1);
		if (index == size) {
			nums.remove(size);
		} else {
			int tail = nums.get(size);
			List<Integer> tails = ids.get(tail);
			nums.set(index, tail);// 这是一手set比add好做 62.64%
//			nums.remove(index);// 替换set 27.47%
//			nums.add(index, tail);// 替换set 27.47%
			tails.remove((Object) size);
			tails.add(index);
			nums.remove(size);
		}
		if (id.size() == 0) {
			ids.remove(val);
		}
		return true;
	}

	public int getRandom() {
		return nums.get((int) (Math.random() * size));
	}

	public static void main(String[] args) {
		// 初始化一个空的集合。
		RandomizedCollection2 collection = new RandomizedCollection2();

		collection.insert(0);
		collection.remove(0);
		collection.insert(-1);
		collection.remove(0);

//		collection.insert(1);
//		collection.remove(1);
//		collection.insert(1);

//		collection.insert(1);
//		collection.insert(1);
//		collection.insert(2);
//		collection.insert(2);
//		collection.insert(2);
//		collection.remove(1);
//		collection.remove(1);
//		collection.remove(2);
//		collection.insert(1);
//		collection.remove(2);
		System.out.println(collection.getRandom());
		System.out.println(collection.getRandom());
		System.out.println(collection.getRandom());
		System.out.println(collection.getRandom());
		System.out.println(collection.getRandom());
		System.out.println(collection.getRandom());
		System.out.println(collection.getRandom());
		System.out.println(collection.getRandom());
		System.out.println(collection.getRandom());
		System.out.println(collection.getRandom());

	}

	public static void test() {
		// 初始化一个空的集合。
		RandomizedCollection2 collection = new RandomizedCollection2();

		// 向集合中插入 1 。返回 true 表示集合不包含 1 。
		collection.insert(1);

		// 向集合中插入另一个 1 。返回 false 表示集合包含 1 。集合现在包含 [1,1] 。
		collection.insert(1);

		// 向集合中插入 2 ，返回 true 。集合现在包含 [1,1,2] 。
		collection.insert(2);

		// getRandom 应当有 2/3 的概率返回 1 ，1/3 的概率返回 2 。
		System.out.println(collection.getRandom());

		// 从集合中删除 1 ，返回 true 。集合现在包含 [1,2] 。
		collection.remove(1);

		// getRandom 应有相同概率返回 1 和 2 。
		System.out.println(collection.getRandom());
	}

}
